class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length(), m = p.length();
        // dp[i][j]  表示 s 从 0 到 i 和 p 从 0 到 j 是否可以匹配
        boolean[][] dp = new boolean[n + 1][m + 1];
        boolean flag = true;
        dp[0][0] = true;
        for (int j = 1; j <= m; j++) {
            if (p.charAt(j - 1) != '*') {
                flag = false;
            }
            dp[0][j] = flag;
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char c1 = s.charAt(i - 1);
                char c2 = p.charAt(j - 1);
                if (c2 == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (c2 == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j - 1] && c1 == c2;
                } 
            }
        }
        return dp[n][m];
    }
}